// Copyright 2011, Vanya Davidenko.
// Кодировка файла: UTF-8. 
package info.iu9.red;
import info.iu9.UnicodeMap;
import info.iu9.interval_tree.*;
import java.util.*;



class Parser {
  Parser(final String pattern) {
    pattern_ = pattern;
    pos_ = 0;
  }

  FiniteAutomata parse() throws RegexException {
    final FiniteAutomata fa = regex();
    fa.append(new MatchState());

    if ( !isEol() ) {
      throw new RegexException(errMsg("EOL expected but not found"));
    }

    return fa;
  }

  private FiniteAutomata regex() throws RegexException {
    return alternative();
  }

  private FiniteAutomata alternative() throws RegexException {
    final FiniteAutomata fa = concatenation();
    while ( currentChar() == '|' ) {
      skip('|');
      fa.alternative(concatenation());
    }
    return fa;
  }

  private FiniteAutomata concatenation() {
    final FiniteAutomata fa = new FiniteAutomata();
    while ( isAnchoringFirst() ) {
      fa.append(anchoring());
    }
    return fa;
  }


  private FiniteAutomata anchoring() throws RegexException {
    final FiniteAutomata fa = new FiniteAutomata();
    if ( currentChar() == '^' ) {
      skip('^');
      if ( is_multiline_ ) {
        fa.append(new MultiLineBeginningAnchorState());
      } else {
        fa.append(new BeginningAnchorState());
      }
    }

    if ( isRepeatFirst() ) {
      fa.append(repeat());
    }

    if ( currentChar() == '$' ) {
      skip('$');
      if ( is_multiline_ ) {
        fa.append(new MultiLineEndingAnchorState());
      } else {
        fa.append(new EndingAnchorState());
      }
    }
    return fa;
  }

  private FiniteAutomata repeat() {
    verify(isRepeatFirst());

    final FiniteAutomata fa = simple();

    final int c = currentChar();
    IntInterval r = null;
    switch ( c ) {
      case '?':
      case '*':
      case '+': moveChar(); break;
      default:
        if ( isRepeatIntervalFirst() ) {
          r = repeatInterval();
        } else {
          return fa;  // нет квантификаторов
        }
    }

    final boolean lazy = currentChar() == '?';
    if ( lazy ) {
      skip('?');
    }
    switch ( c ) {
      case '?': fa.zeroOrOne(lazy); break;
      case '*': fa.zeroOrMore(lazy); break;
      case '+': fa.oneOrMore(lazy); break;
      default: fa.range(lazy, r.min(), r.max());
    }
    return fa;
  }

  private IntInterval repeatInterval() {
    verify(isRepeatIntervalFirst());
    skip('{');

    final int min = parseNumber(0, RANGE_INFINITE - 1, 10);
    int max = min;

    if ( currentChar() == ',' ) {
      skip(',');
      if ( isDigit() ) {
        max = parseNumber(0, RANGE_INFINITE - 1, 10);
      }
      else {
        max = RANGE_INFINITE;
      }
    }

    skip('}');
    return new IntInterval(min, max);
  }

  private FiniteAutomata simple() {
    verify(isSimpleFirst());

    if ( isGroupFirst() ) {
      return group();
    }
    return atom();
  }

  private FiniteAutomata group() {
    verify(isGroupFirst());
    skip('(');

    // По умолчанию, все скобки сохраняющие.
    is_non_capturing_group_ = false;

    // По умолчанию, значения флагов определяются внешними значениями.
    final boolean saved_is_case_sensetive = is_case_insensetive_;
    final boolean saved_is_multiline = is_multiline_;
    final boolean saved_is_dot_all = is_dot_all_;
    final boolean saved_is_non_capturing_group = is_non_capturing_group_;

    if ( isSpecialGroupPrefixFirst() ) {
      specialGroupPrefix();
    }

    final FiniteAutomata fa = new FiniteAutomata();

    if ( !is_non_capturing_group_ ) {
      final int saved_next_submatch_num = next_capturing_group_num_++;
      fa.append(new BeginSaveState(saved_next_submatch_num));
      fa.append(regex());
      fa.append(new EndSaveState(saved_next_submatch_num));
    } else {
      fa.append(regex());
    }

    is_case_insensetive_ = saved_is_case_sensetive;
    is_multiline_ = saved_is_multiline;
    is_dot_all_ = saved_is_dot_all;
    is_non_capturing_group_ = saved_is_non_capturing_group;

    skip(')');
    return fa;
  }

  private void specialGroupPrefix() {
    verify(isSpecialGroupPrefixFirst());
    skip('?');

    if ( isCapturingGroupFlagsFirst() ) {
      // Заменяет флаги, они сохранены выше
      while ( isCapturingGroupFlagsFirst() ) {
        capturingGroupFlags();
      }
    } else {
      is_non_capturing_group_ = true;
    }

    skip(':');
  }

  private void capturingGroupFlags() {
    verify(isCapturingGroupFlagsFirst());

    switch ( currentChar() ) {
      case 'i': skip('i'); is_case_insensetive_ = true; break;
      case 'I': skip('I'); is_case_insensetive_ = false; break;
      case 'm': skip('m'); is_multiline_ = true; break;
      case 'M': skip('M'); is_multiline_ = false; break;
      case 's': skip('s'); is_dot_all_ = true; break;
      case 'S': skip('S'); is_dot_all_ = false; break;
      case 'n': skip('n'); is_non_capturing_group_ = true; break;
      default:
       throw new RegexException(errMsg("Unknown capturing group flag"));
    }
  }

  private FiniteAutomata atom() {
    verify(isOneCharacterFirst());

    final State s;
    // семантика: здесь может быть любая escape-последовательность
    if ( isEscapeSequenceFirst() ) {
      s = escapeSequence();

    } else if ( currentChar() == '.' ) {
      skip('.');
      s = is_dot_all_ ? new DotAllState() : new DotState();

    } else if ( isCharacterClassFirst() ) {
      s = characterClass();

    } else if ( isSpecialCharacter() ) {
      throw new RuntimeException("atom");

    } else if ( is_case_insensetive_ ) {
      s = new CaseCharacterState(moveChar());

    } else {
      s = new CharacterState(moveChar());
    }

    return new FiniteAutomata(s);
  }

  private State characterClass() {
    verify(isCharacterClassFirst());
    skip('[');

    final IntervalTree tree = isNonMatchingCharacterClassFirst() ?
                              nonMatchingCharacterClass() :
                              matchingCharacterClass();

    final IntervalSearchSet set = tree.compile();

    final State result = is_case_insensetive_ ?
                         new CaseCharacterGroupState(set) :
                         new CharacterGroupState(set);


    skip(']');
    return result;
  }

  private IntervalTree matchingCharacterClass() {
    return chracterClassContent();
  }

  private IntervalTree nonMatchingCharacterClass() {
    verify(isNonMatchingCharacterClassFirst());
    skip('^');
    return makeIntervalTree(invertIntervals(chracterClassContent()));
  }

  private IntervalTree chracterClassContent() {
    final Collection<IntInterval> i = isCharacterClassFirstBracketFirst() ?
                                      characterClassFirstBracket() :
                                      characterClassFirstElse();
    return makeIntervalTree(i);
  }

  private Collection<IntInterval> characterClassFirstBracket() {
    verify(isCharacterClassFirstBracketFirst());
    skip(']');

    final Collection<IntInterval> intervals = new ArrayList<IntInterval>();
    intervals.add(new IntInterval(']', ']'));

    while ( isCharacterGroupFirst() ) {
      intervals.addAll(characterGroup());
    }

    return intervals;
  }

  private Collection<IntInterval> characterClassFirstElse() {
    final Collection<IntInterval> intervals = new ArrayList<IntInterval>();
    do {
        intervals.addAll(characterGroup());
    } while( isCharacterGroupFirst() );

    return intervals;
  }

  private Collection<IntInterval> characterGroup() {
    verify(isCharacterGroupFirst());

    // Возможно 3 варианта:
    //  - встречается escape-последовательность, обозначающая интервал (\\d),
    //    исходя из семантики, она не может быть началом символьной группы
    //    ([a-z]), поэтому сразу возвращается методом.
    //  - встречается escape-последовательность, обозначающая один символ,
    //    тогда intervalEscapeSequence() возвращает тривиальный набор интервалов
    //    (один интервал, с равными границами), которая может быть началом
    //    символьной группы
    //  - встречается обычный символ, который может быть началом символьной
    //    группы.

    // Семантика: в символьной группе встречаются:
    //  - escape-последовательности, обозначающие интервалы (\\d, \\pC, \\xFF)
    //  - один символ.
    // В случае, если возвращаемый интервал тривиален (один символ или \\xFF,
    // обозначающий один символ) — это может быть левой границей интервала.

    final List<IntInterval> left = characterGroupLeftBoundary();

    if ( !isCharacterGroupEndFirst() ) {  // не интервал
      return left;
    }

    // Левой границей интервала не может быть интервал: [\\d-0].
    if ( left.size() != 1 || left.get(0).min() != left.get(0).max() ) {
      throw new RegexException(errMsg("Bad left boundary"));
    }

    return characterGroupEnd(left.get(0).min());
  }

  // Из-за того, что грамматика не LL(1) (вероятно) — по следующему токену
  // '-' невозможно определить что это: спец. символ, обозначающий интервал
  // (a-z) или знак "минус",стоящий в конце — необходимо смотреть на 2 символа.
  private Collection<IntInterval> characterGroupEnd(final int l) {
    verify(isCharacterGroupEndFirst());
    skip('-');

    // Интервал: [l-oneCharacter()]. Пример: [a-z].
    if ( isOnecharacterFirst() ) {
        return Arrays.asList(new IntInterval(l, characterGroupRightBoundary()));

    // Пара: l и знак "минус". Пример: [a-].
    } else {
      return Arrays.asList(new IntInterval(l, l), new IntInterval('-', '-'));
    }
  }

  private List<IntInterval> characterGroupLeftBoundary() {
    if ( isEscapeSequenceFirst() ) {
      return intervalEscapeSequence();
    } else {
      final int c = oneCharacter();
      return Arrays.asList(new IntInterval(c, c));
    }
  }

  private int characterGroupRightBoundary() {
    return oneCharacter();
  }

  private int oneCharacter() {
    verify(isOnecharacterFirst());

    if ( isEscapeSequenceFirst() ) {
      return characterEscapeSequence();

    } else if ( currentChar() != ']' ) {
      return moveChar();

    } else {
      assert currentChar() == ']';
      throw new RuntimeException("oneCharacter");
    }
  }

  // Любая escape-последовательность, обозначающее одно из состояний:
  //  - якорь (\\A, \\z)
  //  - интервал символов, см. intervalEscapeSequence.
  private State escapeSequence() {
    verify(isEscapeSequenceFirst());
    skip('\\');

    if ( isAnchorEscapeSequenceFirst() ) {
      return anchorEscapeSequence();
    } else {
      moveCharBack();

      final IntervalTree t = makeIntervalTree(intervalEscapeSequence());
      final IntervalSearchSet s = t.compile();

      return is_case_insensetive_ ?
             new CaseCharacterGroupState(s) :
             new CharacterGroupState(s);
    }
  }

  // Escape-последовательность, обозначающая набор интервалов:
  //  - \\p{Cyrillic}
  //  - \\d, \\w, ...
  //  - или один символ (тривиальный интервал), см. characterEscapeSequence.
  private List<IntInterval> intervalEscapeSequence() {
    verify(isEscapeSequenceFirst());
    skip('\\');

    if ( isIncludeUnicodePropertyFirst() ) {
      return includeUnicodeProperty();

    } else if ( isExcludeUnicodePropertyFirst() ) {
      return excludeUnicodeProperty();

    } else if ( isPerlCharacterClassFirst() ) {
      return perlCharacterClass();

    } else {
      moveCharBack();
      final int c = characterEscapeSequence();
      return Arrays.asList(new IntInterval(c,c));
    }
  }

  // Escape-последовательность, обозначающая один символ:
  //  - \^, \$, ...
  //  - \\xFF, \\X{100}
  private int characterEscapeSequence() {
    verify(isEscapeSequenceFirst());
    skip('\\');

    if ( isSpecialCharacter() ) {
       return moveChar();
    } else if ( isCharacterCodeFirst() ) {
      return characterCode();
    }

    throw new RegexException(errMsg("Bad escape sequence"));
  }

  private State anchorEscapeSequence() {
    verify(isAnchorEscapeSequenceFirst());

    switch ( moveChar() ) {
      case 'A': return new StringBeginningAnchorState();
      case 'Z': return new StringEndingAnchorState();
      case 'z': return new EndOfStringAnchorState();
      case 'b': return new WordBoundaryAnchorState();
      case 'B': return new InvertedWordBoundaryAnchorState();
      default:
        assert false;
        return null;
    }
  }

  private List<IntInterval> includeUnicodeProperty() {
    verify(isIncludeUnicodePropertyFirst());
    skip('p');
    return unicodeProperty();
  }

  private List<IntInterval> excludeUnicodeProperty() {
    verify(isExcludeUnicodePropertyFirst());
    skip('P');
    return invertIntervals(unicodeProperty());
  }

  private List<IntInterval> unicodeProperty() {
    final String name = isFullCharacterUnicodeClassNameFirst() ?
                        fullCharacterUnicodeClassName() :
                        oneLetterUnicodeCharacterClassName();

    final List<IntInterval> result = UnicodeMap.get(name);
    if ( result == null ) {
      throw new RegexException(errMsg("Unknown unicode class name"));
    }
    return result;
  }

  private String oneLetterUnicodeCharacterClassName() {
    return Integer.toString(moveChar());
  }

  private String fullCharacterUnicodeClassName() {
    verify(isFullCharacterUnicodeClassNameFirst());
    skip('{');

    final StringBuilder sb = new StringBuilder();
    do {
      sb.appendCodePoint(moveChar());
    } while ( currentChar() != '}' );
    skip('}');

    return sb.toString();
  }

  private List<IntInterval> perlCharacterClass() {
    final int c = moveChar();
    switch ( c ) {
      case 'd':
      case 'D':
        final List<IntInterval> d = Arrays.asList(new IntInterval('0', '9'));
        return c == 'D' ? invertIntervals(d) : d;

      case 's':
      case 'S':
        final List<IntInterval> s = Arrays.asList(new IntInterval('\t', '\t'),
                                                  new IntInterval('\n', '\n'),
                                                  new IntInterval('\f', '\f'),
                                                  new IntInterval('\r', '\r'),
                                                  new IntInterval(' ', ' '));
        return c == 'S' ? invertIntervals(s) : s;

      case 'w':
      case 'W':
        final List<IntInterval> w = Arrays.asList(new IntInterval('0', '9'),
                                                  new IntInterval('a', 'z'),
                                                  new IntInterval('A', 'Z'),
                                                  new IntInterval('_', '_'));
        return c == 'W' ? invertIntervals(w) : w;

      default:
        assert false;
        return null;
    }
  }

  private int characterCode() {
    verify(isOnecharacterFirst());
    skip('x');

    final String string_hex_value = isLongCharactedCodeFirst() ?
                                    longCharacterCode() :
                                    shortCharacterCode();

    final int value;
    try {
      value = Integer.parseInt(string_hex_value, 16);
    } catch(NumberFormatException e) {
      throw new RegexException(errMsg("Bad character code"));
    }

    if ( value < 0 || value > UNICODE_MAX_ ) {
      throw new RegexException(errMsg("Not a unicode code point"));
    }

    return value;
  }

  private String longCharacterCode() {
    verify(isLongCharactedCodeFirst());
    skip('{');

    final StringBuilder sb = new StringBuilder();
    do {
      sb.appendCodePoint(moveChar());
    } while ( currentChar() != '}' );
    skip('}');

    return sb.toString();
  }

  private String shortCharacterCode() {
    final StringBuilder sb = new StringBuilder(2);
    sb.appendCodePoint(moveChar());
    sb.appendCodePoint(moveChar());
    return sb.toString();
  }


  private int currentChar() {
    if ( isEol() ) {
      return 0;
    } else if ( Character.isLowSurrogate(pattern_.charAt(pos_)) ) {
      throw new RegexException(errMsg("Low surrogate found"));
    }

    return pattern_.codePointAt(pos_);
  }

  private boolean isEol() {
    return pos_ == pattern_.length();
  }

  private int moveChar() {
    final int result = currentChar();
    pos_ = pattern_.offsetByCodePoints(pos_, 1);
    return result;
  }

  private void skip(final int ch) {
    if ( moveChar() != ch ) {
      final StringBuilder sb = new StringBuilder();
      sb.append('\'');
      sb.appendCodePoint(ch);
      sb.append('\'');
      sb.append(" expected, but not found");
      throw new RuntimeException(errMsg(sb.toString()));
    }
  }

  private void moveCharBack() {
    pos_ = pattern_.offsetByCodePoints(pos_, -1);
  }

  private static void verify(final boolean b) {
    if ( !b ) {
      throw new RuntimeException("Internal error");
    }
  }

  private int parseNumber(final int min, final int max, final int radix) {
    final StringBuilder sb = new StringBuilder();
    if ( !isDigit(currentChar()) ) {
      throw new RegexException(errMsg("Digit expected"));
    }
    while ( isDigit(currentChar()) ) {
      sb.appendCodePoint(moveChar());
    }

    try {
      final int result = Integer.parseInt(sb.toString(), radix);
      if ( result > max || result < min ) {
        throw new RegexException(errMsg("Bad number"));
      }
      return result;
    } catch(NumberFormatException e) {
      throw new RegexException(errMsg("Not a number"));
    }
  }

  private static boolean isDigit(final int c) {
    return Character.digit(c, 10) != -1;
  }

  private static boolean isHexDigit(final int c) {
    return Character.digit(c, 16) != -1;
  }


  private boolean isDigit() {
    return isDigit(currentChar());
  }

  private boolean isAsciiLetterDigitCharacter() {
    final int c = currentChar();
    return isDigit(c) || 'a' <= c && c <= 'z' || 'A' <= c && c <= 'Z';
  }

  private boolean isConcatenationFirst() {
    return isAnchoringFirst();
  }

  private boolean isAnchoringFirst() {
    final int c = currentChar();
    return c == '^' || isRepeatFirst() || c == '$';
  }

  private boolean isRepeatFirst() {
    return isSimpleFirst();
  }

  private boolean isRepeatIntervalFirst() {
    return currentChar() == '{';
  }

  private boolean isGroupFirst() {
    return currentChar() == '(';
  }

  private boolean isSimpleFirst() {
    return isOneCharacterFirst() || isGroupFirst();
  }

  private boolean isSpecialGroupPrefixFirst() {
    return currentChar() == '?';
  }

  private boolean isOneCharacterFirst() {
    return !isEol() &&
           ( isEscapeSequenceFirst() ||
             currentChar() == '.' ||
             isCharacterClassFirst() ||
             !isSpecialCharacter() );
  }

  private boolean isCapturingGroupFlagsFirst() {
    switch ( currentChar() ) {
      case 'i':
      case 'I':
      case 'm':
      case 'M':
      case 's':
      case 'S':
      case 'n': return true;
      default: return false;
    }
  }

  private boolean isEscapeSequenceFirst() {
    return currentChar() == '\\';
  }

  private boolean isAnchorEscapeSequenceFirst() {
    switch ( currentChar() ) {
      case 'A':
      case 'Z':
      case 'z':
      case 'b':
      case 'B':
        return true;
      default:
        return false;
    }
  }

  private boolean isIncludeUnicodePropertyFirst() {
    return currentChar() == 'p';
  }

  private boolean isExcludeUnicodePropertyFirst() {
    return currentChar() == 'P';
  }

  private boolean isFullCharacterUnicodeClassNameFirst() {
    return currentChar() == '{';
  }

  private boolean isCharacterCodeFirst() {
    return currentChar() == 'x';
  }

  private boolean isPerlCharacterClassFirst() {
    switch ( currentChar() ) {
      case 'd':
      case 'D':
      case 's':
      case 'S':
      case 'w':
      case 'W':
        return true;
      default:
        return false;
    }
  }

  private boolean isLongCharactedCodeFirst() {
    return currentChar() == '{';
  }

  private boolean isCharacterClassFirst() {
    return currentChar() == '[';
  }

  private boolean isNonMatchingCharacterClassFirst() {
    return currentChar() == '^';
  }

  private boolean isCharacterClassFirstBracketFirst() {
    return currentChar() == ']';
  }

  private boolean isSpecialCharacter() {
    switch ( currentChar() ) {
      case '^':
      case '$':
      case '(':
      case ')':
      case '.':
      case '[':
      case '|':
      case '?':
      case '*':
      case '+':
      case '{':
      case '}':
      case '\\':
        return true;
      default:
        return false;
    }
  }

  private boolean isCharacterGroupFirst() {
    return isOnecharacterFirst();
  }

  private boolean isCharacterGroupEndFirst() {
    return currentChar() == '-';
  }

  private boolean isOnecharacterFirst() {
    return !isEol() && currentChar() != ']';
  }

  private static boolean isUnicodeChar(final int c) {
    return 0 <= c && c <= UNICODE_MAX_;
  }

  private String errMsg(final String msg) {
    return msg + " at position: " + Integer.toString(pos_);
  }



  // Инвертирование списка интервалов: построение списка интервалов
  // всех юникодных символов (от 0 до 0x10FFFF) не входящих в заданный.
  // В случае, если текущий режим не multiline, то символы '\n' и '\r'
  // также исключаются из результата.
  // Эту операцию могло реализовывать дерево интервалов, но формально
  // оно не знает о границах юникодных символов.
  private List<IntInterval> invertIntervals(final Iterable<IntInterval> l) {
    final IntervalTree t = new IntervalTree();
    for ( final IntInterval i : l ) {
      assert isUnicodeChar(i.min()) && isUnicodeChar(i.max());
      t.insert(i);
    }

    if ( !is_multiline_ ) {
      t.insert(new IntInterval('\n', '\n'));
    }

    t.shrink();

    final List<IntInterval> result = new ArrayList<IntInterval>();
    int prev = 0;
    for ( final IntInterval i : t ) {
      // Условие может быть истинным только на самом первом интервале: [0, ...].
      if ( i.min() != 0 ) {
        result.add(new IntInterval(prev, i.min() - 1));
      }
      prev = i.max() + 1;
    }
    // Условие истинно, если последний интервал до unicode_max_.
    if ( prev <= UNICODE_MAX_ ) {
      result.add(new IntInterval(prev, UNICODE_MAX_));
    }

    return result;
  }

  private static IntervalTree makeIntervalTree(final Iterable<IntInterval> l) {
    final IntervalTree result = new IntervalTree();
    for ( final IntInterval i : l ) {
      result.insert(i);
    }
    return result;
  }

  private static boolean containsTrivialInterval(final List<IntInterval> a) {
    return a.size() == 1 && a.get(0).min() == a.get(0).max();
  }


  private final String pattern_;
  private int pos_;

  private boolean is_case_insensetive_ = false;
  private boolean is_dot_all_ = false;
  private boolean is_multiline_ = false;
  private boolean is_non_capturing_group_ = false;

  // Являются частью результата парсинга.
  private int next_capturing_group_num_ = 0;

  static final int RANGE_INFINITE = Integer.MAX_VALUE;
  private static final int UNICODE_MAX_ = 0x10FFFF;
}
